package thired.class07_Trie;

import java.util.HashMap;

public class Class01_Trie {

//数组
    public class Trie1{

        class Node1{
            public int pass;
            public int end;
            public Node1[] nexts;

            public Node1(){
                pass = 0;
                end = 0;
                nexts = new Node1[26];
            }
        }


        public Node1 root;

        public Trie1(){
            root = new Node1();
        }

        public void insert(String word){
            if(word == null){
                return;
            }
            char[] str = word.toCharArray();
            Node1 node1 = root;
            node1.pass++;
            int path = 0;
            for (int i = 0; i < str.length; i++) {
                path = str[i] - 'a';
                if(node1.nexts[path] == null){
                    node1.nexts[path] = new Node1();
                }
                node1 = node1.nexts[path];
                node1.pass++;
            }
            node1.end++;
        }

        public int countWordsEqualTo(String word){
            if (word == null) {
                return 0;
            }
            char[] str = word.toCharArray();
            Node1 node = root;
            int path = 0;
            for (int i = 0; i < str.length; i++) {
                path = str[i] - 'a';
                if (node.nexts[path] == null) {
                    return 0;
                }
                node = node.nexts[path];
            }
            return node.end;
        }

        public void erase(String word){
            if(countWordsEqualTo(word) == 0){
                return;
            }
            char[] str = word.toCharArray();
            Node1 node = root;
            node.pass--;
            int path = 0;
            for (int i = 0; i < str.length; i++) {
                path = str[i] - 'a';
                if(--node.nexts[path].pass == 0){
                    node.nexts[path] = null;
                    return;
                }
                node = node.nexts[path];
            }
            node.end--;
        }

        public int countWordsStartWith(String word){
            if (word == null) {
                return 0;
            }
            char[] str = word.toCharArray();
            Node1 node = root;
            int path = 0;
            for (int i = 0; i < str.length; i++) {
                path = str[i] - 'a';
                if (node.nexts[path] == null) {
                    return 0;
                }
                node = node.nexts[path];
            }
            return node.pass;

        }
    }

//hash
    public class Trie2{

        class Node2{
            public int pass;
            public int end;
            public HashMap<Integer,Node2> nexts;

            public Node2(){
                pass = 0;
                end = 0;
                nexts = new HashMap<>();
            }
        }


        public Node2 root;

        public Trie2(){
            root = new Node2();
        }

        public void insert(String word){
            if(word == null){
                return;
            }
            char[] str = word.toCharArray();
            Node2 node = root;
            node.pass++;
            int path = 0;
            for (int i = 0; i < str.length; i++) {
                path = str[i] - 'a';
                if(!node.nexts.containsKey(path)){
                    node.nexts.put(path,new Node2());
                }
                node = node.nexts.get(path);
                node.pass++;
            }
            node.end++;
        }

        public int countWordsEqualTo(String word){
            if (word == null) {
                return 0;
            }
            char[] str = word.toCharArray();
            Node2 node = root;
            int path = 0;
            for (int i = 0; i < str.length; i++) {
                path = str[i] - 'a';
                if (!node.nexts.containsKey(path)) {
                    return 0;
                }
                node = node.nexts.get(path);
            }
            return node.end;
        }

        public void erase(String word){
            if(countWordsEqualTo(word) == 0){
                return;
            }
            char[] str = word.toCharArray();
            Node2 node = root;
            node.pass--;
            int path = 0;
            for (int i = 0; i < str.length; i++) {
                path = str[i] - 'a';
                if(--node.nexts.get(path).pass == 0){
                    node.nexts.remove(path);
                    return;
                }
                node = node.nexts.get(path);
            }
            node.end--;
        }

        public int countWordsStartWith(String word){
            if (word == null) {
                return 0;
            }
            char[] str = word.toCharArray();
            Node2 node = root;
            int path = 0;
            for (int i = 0; i < str.length; i++) {
                path = str[i] - 'a';
                if (node.nexts.get(path) == null) {
                    return 0;
                }
                node = node.nexts.get(path);
            }
            return node.pass;

        }
    }
}
